The Hierarchical Heavy Hitters problem extends the notion of frequent itemsto data arranged in a hierarchy. This problem has applications to networktraffic monitoring, anomaly detection, and DDoS detection. We present a newstreaming approximation algorithm for computing Hierarchical Heavy Hitters thathas several advantages over previous algorithms. It improves on the worst-casetime and space bounds of earlier algorithms, is conceptually simple andsubstantially easier to implement, offers improved accuracy guarantees, iseasily adopted to a distributed or parallel setting, and can be efficientlyimplemented in commodity hardware such as ternary content addressable memory(TCAMs). We present experimental results showing that for parameters of primarypractical interest, our two-dimensional algorithm is superior to existingalgorithms in terms of speed and accuracy, and competitive in terms of space,while our one-dimensional algorithm is also superior in terms of speed andaccuracy for a more limited range of parameters.
展开▼
